Corelab Seminar
2010-2011
Christos Tzamos
Winner-Imposing Strategyproof Mechanisms for Multiple Facility Location Games
Abstract.
We study Facility Location games, where a number of facilities are placed in a metric
space based on locations reported by strategic agents. A mechanism maps the agents' locations to a set of facilities.
The agents seek to minimize their connection cost, namely the distance of their true location to the nearest facility,
and may misreport their location. We are interested in mechanisms that are strategyproof, do not resort to monetary
transfers, and approximate the optimal social cost. We focus on the closely related problems of k-Facility Location
and Facility Location with a uniform facility opening cost, instead of a fixed number of facilities.
We mostly study winner-imposing mechanisms, which allocate facilities to the agents and require that
each agent allocated a facility should connect to it. We show that the winner-imposing version
of the Proportional Mechanism [Lu et al., EC '10] is stategyproof and 4k-approximate for the k-Facility Location game,
for any k. For the Facility Location game, we show that the winner-imposing version of the randomized algorithm
of [Meyerson, FOCS '01], which hasan approximation ratio of 8, is strategyproof.
Furthermore, we present a deterministic non-imposing group strategyproof O(log n)-approximate mechanism for
the Facility Location game on the line.